#include "BinaryTree.h"
#include<iostream>
#include<linkQueen.h>
BinaryTree::BinaryTree()
{
    root=nullptr;
}

BinaryTree::~BinaryTree()
{
    FreeNode(root);
}

void BinaryTree::Insert(const ElementType &element)
{
    root=InsertNode(root,element);
}

BinaryTree::ElementType *BinaryTree::FindElement(const ElementType &element)
{
   return FindNode(root,element);
}

void BinaryTree::Remove(const ElementType &element)
{
    root=RemoveNode(root,element);
}

void BinaryTree::show()
{
    std::cout<<"前：";
    PrevTravel(root);
    std::cout<<std::endl;
     std::cout<<"中：";
     MidTravel(root);
    std::cout<<std::endl;
     std::cout<<"后：";
    PostvTravel(root);
    std::cout<<std::endl;

    std::cout<<"层：";
    linkQueen q;
    q.push(root);
    while(q.isEmpty()==false)
    {
         TreeNode* node=(TreeNode*)*q.getFront();
         q.pop();
         print(node->date);
         if(node->Left)
            q.push(node->Left);
        if(node->right)
            q.push(node->right);
    }
     std::cout<<std::endl;
}

BinaryTree::TreeNode* BinaryTree::InsertNode(TreeNode *node, const ElementType &element)
{
    if(node==nullptr)//如果为空构建
    {
        return new TreeNode(element);
    }
    if(compare(node->date,element))//数据已经存在
    {
        return node;
    }
    else if(cmpBig(node->date,element))
    {
          node->Left=InsertNode(node->Left,element);
          //左边重失衡
          if(LRDeviation(node)>1)
          {
            //左左失衡
            if(cmpBig(node->Left->date,element))
            {
                //右旋
                node=RotateRight(node);
            }
            //左右失衡
            else
            {
                //左右旋
                node=RotateLeftRight(node);
            }
          }
    }
    else{
        node->right=InsertNode(node->right,element);
        //右边重失衡
        if(LRDeviation(node)<-1)
        {
            //右右失衡
            if(element>node->right->date)
            {
                node=RotateLeft(node);
            }
            else
            {
                node=RotateRightLeft(node);
            }
        }
    }
    return node;   
}

void BinaryTree::PrevTravel(TreeNode *node)
{
    if(node==nullptr)
        return;
    print(node->date);
    PrevTravel(node->Left);
    PrevTravel(node->right);
}

void BinaryTree::MidTravel(TreeNode *node)
{
    if(node==nullptr)
        return;
    MidTravel(node->Left);
    print(node->date);
    MidTravel(node->right);
}

void BinaryTree::PostvTravel(TreeNode *node)
{
    if(node==nullptr)
        return;
    PostvTravel(node->Left);
    PostvTravel(node->right);
    print(node->date);
}

void BinaryTree::FreeNode(TreeNode *node)
{
    if(node==nullptr)
        return;
    FreeNode(node->Left);
    FreeNode(node->right);
    delete node;

}

BinaryTree:: ElementType *BinaryTree::FindNode(TreeNode *node, const ElementType &element)
{
    if(node==nullptr)
        return nullptr;
    if(compare(node->date,element))
        return &node->date;
    if(cmpBig(element, node->date))
        return FindNode(node->right,element);
    if(cmpBig( node->date,element))
        return FindNode(node->Left,element);
    return nullptr;
}

BinaryTree::TreeNode *BinaryTree::RemoveNode(TreeNode *node, const ElementType &element)
{
   if(node ==nullptr)
        return nullptr;
    if(cmpBig(element, node->date))
    {
        node->right=RemoveNode(node->right,element);
    }
    else if(cmpBig(node->date,element))
    {
        node->Left=RemoveNode(node->Left,element);
    }
    else
    {
       //叶子
       if(node->Left==nullptr&&node->right==nullptr)
       {
           delete node;
           return nullptr;   
       }
       //左右孩子都存在
       else if(node->Left!=nullptr&&node->right!=nullptr)
       {
        //取右子树中最小节点
            TreeNode *min=GetMinNode(node->right);
        //将最小节点的值赋给node
            node->date=min->date;
        //删掉最小节点
            node->right=RemoveNode(node->right,min->date);
        
       }
       //只有一个孩子
       else
       {
            TreeNode *childNode=node->Left?node->Left:node->right;
            delete node;
            node= childNode;
       }
    }
     if(LRDeviation(node)>1)
          {
            //左左失衡
            if(LRDeviation(node->Left)>0)//左边高度比右边高
            {
                //右旋
                node=RotateRight(node);
            }
            //左右失衡
            else
            {
                //左右旋
                node=RotateLeftRight(node);
            }
          }
     if(LRDeviation(node)<-1)
        {
            //右右失衡
            if(LRDeviation(node->right)<0)//右边高度比左边高
            {
                node=RotateLeft(node);
            }
            else
            {
                node=RotateRightLeft(node);
            }
        }

  
    //同一判断返回node
    return node;
}

BinaryTree:: TreeNode *BinaryTree::GetMinNode(TreeNode*node)
{
    TreeNode *MinNode=node;
    while(node->Left!=nullptr)
        MinNode=MinNode->Left;
    return MinNode;
}

BinaryTree:: TreeNode *BinaryTree::RotateRight(TreeNode *node)
{
    TreeNode *t=node->Left;
    node->Left=t->right;
    t->right=node;
    return t;
}

BinaryTree:: TreeNode *BinaryTree::RotateLeft(TreeNode *node)
{
    TreeNode *t=node->right;
    node->right=t->Left;
    t->Left=node;
    return t;
}

BinaryTree:: TreeNode *BinaryTree::RotateLeftRight(TreeNode *node)
{
    //左子树左旋
    node->Left=RotateLeft(node->Left);
    //整棵树右旋
    return  RotateRight(node);
}

BinaryTree:: TreeNode *BinaryTree::RotateRightLeft(TreeNode *node)
{
  //右子树右旋
  node->right=RotateRight(node->right);
  //整棵树左旋
  return RotateLeft(node);
}

int BinaryTree::GetNodeHeight(TreeNode *node)
{
    if(node==nullptr)
        return 0;
    int leftHeight=GetNodeHeight(node->Left);
    int RightHeight=GetNodeHeight(node->right);
    return (leftHeight>RightHeight?leftHeight:RightHeight)+1;
    
}

int BinaryTree::LRDeviation(TreeNode *node)
{
    if(node==nullptr)
        return 0;
    return GetNodeHeight(node->Left)-GetNodeHeight(node->right);
}
